

import java.util.Arrays;
import java.util.Random;

// 遗传算法 求解 TSP 问题

public class Solution {

    private double sum;

    Me me = new Me();

   /* class me {
        int fit;
        double el;
        double q;
        int[] code;
        int[] path;
    }*/

    public int[] init(int length) {
        int[] pc = new int[length];
        Random r = new Random();
        for (int i = 0; i < length; i++){
            if (i != 0){
                pc[i] = r.nextInt(length - i) + 1;
            }else{
                pc[i] = 1;
                // 将第一个位置设置为1
            }
        }
        return pc;
    }




    public int fitnum(int[] path, int[][] dis) {
        int len = 0;
        int size = path.length;
        for (int i = 0; i < size - 1; i++) {
            len = dis[path[i] - 1][path[i + 1] - 1] + len;
        }

        len += dis[path[size - 1] - 1][path[0] - 1];
        // 计算最大适应度
        sum += (double)1/len;
        return len;

    }



    public void first(int[] code1,int[] code2){
        int size = code1.length;
        Random r = new Random();
        int k = 0;
        int ret;
        for(k = r.nextInt(size-1)+1; k < size; k++){
            ret = code1[k];
            code1[k] = code2[k];
            code2[k] = ret;
        }
    }

    public int[] pathchange(int[] code) {
        int size = code.length;
        int[] mark = new int[size];
        int[] path = new int[size];

        for (int i = 0; i < size; i++) {
            int k = 0;
            for (int j = 0; j < size; j++) {
                if (mark[j] != 1) {
                    if (code[i] + k == j + 1) {
                        path[i] = j + 1;
                        mark[j] = 1;
                        break;
                    }
                }else {
                    k++;
                }
            }
        }
        return path;
    }

    public void averageratio(int[] code, double pm){

        int size = code.length;
        int num = (int)( pm * size);
        Random r = new Random();
        int k;
        for(int i=0; i<num; i++){
            k = r.nextInt(size-1) + 1;
            code[k] = 1 + (int)Math.random()*(size - k -1);
        }
    }


    public double fitconnt(int fit) {

        return (double)1/fit/sum;

    }

    public void start(int[][] disance, double ratio, int ling) {
        int total = 6;  // 染色体总数
        int n = 6; // 城市总数
        int[][] dis = disance;
        Me[] mes = new Me[total];

         // 初始化
        for (int i = 0; i < total; i++) {
            mes[i] = new Me();
            mes[i].setCode(init(n));
        }


        for(int xz = 0; xz< ling; xz++ ){
             // 将代码更改为路径
            for (int i = 0; i < total; i++) {
                mes[i].setPath(pathchange(mes[i].getCode()));
            }


            // 计算适合度
            for (int i = 0; i < total; i++) {
                mes[i].setFit(fitnum(mes[i].getPath(),dis));

            }

          // 计算评估结果
            for (int i = 0; i < total; i++) {
                mes[i].setEl(fitconnt(mes[i].getFit()));

            }
         // 计算累积概率q
            for (int i = 0; i < total; i++){
                if(i == 0)
                    mes[i].setQ(mes[i].getEl());
                else
                    mes[i].setQ(mes[i-1].getQ() + mes[i].getEl());
            }


            // 进行选择过程
            int[] chome = new int[total];

            for (int i = 0; i<total; i++){
                double r = Math.random();

                for (int j=0; j<total; j++){
                    if(j == 0){
                        if(0 < r && r < mes[0].getQ()){
                            chome[i] = 0;
                            break;
                        }
                    }
                    else if(mes[j-1].getQ()<r && mes[j].getQ()>r){
                        chome[i] = j;
                        break;
                    }
                }
            }

             // 把儿子传给父亲
            Me[] tempc = new Me[total];
            for(int i=0; i < total; i++)
                tempc[i] = mes[i];
            for(int i=0; i < total; i++){
                mes[i] = new Me();
                mes[i].setCode(new int[n]);
                for(int j=0; j<n; j++)
                    mes[i].getCode()[j]=tempc[chome[i]].getCode()[j];
            }


            //  做交叉动作
            for( int i = 0; i+1 < total; i += 2){
                first(mes[i].getCode(), mes[i+1].getCode());
            }


            for( int i = 0; i < total; i++){
                averageratio(mes[i].getCode(), ratio);
            }

        }

         // 最后一代
        for (int i = 0; i < total; i++) {
            mes[i].setPath(pathchange(mes[i].getCode()));
        }

         // 计算适合度
        for (int i = 0; i < total; i++) {
            mes[i].setFit(fitnum(mes[i].getPath(),dis));
        }

        // 选择最优路径
        int lastnum = 0;
        int lastfit = mes[0].getFit();
        for(int i=0; i< total; i++)
            if(lastfit > mes[i].getFit()){
                lastfit = mes[i].getFit();
                lastnum = i;
            }
        System.out.println("最优路径为 : "+Arrays.toString(mes[lastnum].getPath()));

    }


}